//
// Description: 279. 完全平方数
// Created by Loading on 2022/4/9.
//

#include <bits/stdc++.h>

using namespace std;

/* 数学，四平方和定理：一个正整数至多由 4 个完全平方数的和组成，时间复杂度：O(sqrt(n)) */
int numSquares(int n) {
    // 判断一个数是否是完全平方数
    auto isPerfectSquare = [](int x) {
        int sq = sqrt(x);
        return sq * sq == x;
    };

    if (isPerfectSquare(n)) {
        return 1;
    }

    /* 如果n可以被表示为 4^k*(8m+7) 的形式，则一定至少由4个完全平方数组成 */
    int x = n;
    while (x % 4 == 0) {
        x /= 4;
    }
    if (x % 8 == 7) {
        return 4;
    }

    // 枚举判断是否可以由两个完全平方数构成
    for (int i = 1; i * i <= n; i++) {
        int j = n - i * i;
        if (isPerfectSquare(j)) {
            return 2;
        }
    }
    // 上述情况都不符合，只能由3个完全平方数构成
    return 3;
}

/* 动态规划，时间复杂度：O(n * sqrt(n)) */
int numSquares_DP(int n) {
    vector<int> dp(n + 1, INT_MAX);
    dp[0] = 0;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j * j <= i; ++j) {
            dp[i] = min(dp[i], dp[i - j * j]);
        }
        ++dp[i];
    }

    return dp[n];
}

int main() {
    int n = 9999;
    int res = numSquares(n);
    cout << res << endl;
    res = numSquares_DP(n);
    cout << res << endl;

    return 0;
}